package BinaryTree.前序;

import 其他.DataStructure.TreeNode;
import MyUtils.TreeUtils;
import org.junit.Test;

/**
 * [极重要]
 *      草稿画乱了 -> 并不白画
 *      -> 类似 八股 笔记
 *      -> 重画 立刻 巨 清晰 / 简约
 *
 *
 * 左 LR 末1用 r多用
 */
public class 二叉树展开为链表114 {

    /* 我 */
    // 后序static
    TreeNode dm = new TreeNode(-1);
    public void flatten(TreeNode root) {
        dm = root;
        pre(root);
    }
    private void pre(TreeNode cur) {
        if(cur==null){
            return;
        }

        // 乱指向的 全tmp一下！ -> 递归参数 用
        TreeNode curLeftTmp = cur.left; // 看草稿 -> 末1 不乱 放心
        TreeNode curRightTmp = cur.left;

        dm.right = cur.left;
        cur.left=null;
        dm = dm.left;

        pre(curLeftTmp);
        pre(curRightTmp);
    }
    // 我的 return L/R 中的 最右 思想
    // 草稿跑了一下  ->  可以实现  ->  不如 上面 简单不易错
    TreeNode pre2(TreeNode cur) {
        if(cur==null){
            return cur;
        }

        TreeNode L = pre2(cur.left);
        TreeNode R = pre2(cur.right);

        // 处理 末1 r的N
        if(L==null && R==null){
            return cur;
        }

        // 正常 return;
        // L/R 仅特 接右 用 ，特 ，其他不用
        if(cur.left==null && cur.right!=null){
            return R;
        }
        else if(cur.left!=null && cur.right==null){
            // 处理当前
            cur.right = cur.left;
            cur.left = null;
            // r 接右 用的
            return L;
        }
        else if(cur.left!=null && cur.right!=null){
            TreeNode tmpRight = cur.right;
            // 先 /
            cur.right = cur.left;
            cur.left = null;
            // 后 ——
            L.right = tmpRight;
            return tmpRight;
        }
        return null;//不执行
    }

//    /*
//        LBLD 【太次 不要！】
//
//        后序 [草图画的不好 -> 向右\ 链表   -> 还是不好懂 因为 切到右上子树时 太难想到 这种解法]
//        不过可以 练 后序
//    */
//    public void flatten_lbld(TreeNode root) {
//        back(root);
//    }
//    private void back(TreeNode cur) {
//        if(cur==null){
//            return;
//        }
//
//        TreeNode curLeftTmp = cur.left;
//        TreeNode curRightTmp = cur.right;
//
//        // 右 掰删 至 左
//        cur.right = curLeftTmp;
//        cur.left = null; // 只动左 curLeftTmp 不会gc变null
//
//        // 右接到左尾部
//        while(cur.right != null){ // 这个即找到尾部，又处理了 N时的->N
//            cur = cur.right;
//        }
//        cur.right = curRightTmp;
//
//        back(curLeftTmp);
//        back(curRightTmp); // Tmp作用：1指向 2迭代
//    }


    @Test
    public void test() {
        TreeNode root = TreeUtils.strToTree("1,2,5,3,4,null,6");
        flatten(root);
        System.out.println(1);
    }
}
